package com.leetcode.www;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
 *
 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
 *
 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
 *
 * 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/open-the-lock
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-19
 * Time:21:03
 */
public class BFS752 {
    public int openLock(String[] deadends, String target) {
        if(target == null || target == "0000")return 0;
        Set<String> set = new HashSet<>();//标记位
        Set<String> di = new HashSet<>();
        for(String s: deadends){
            di.add(s);
        }
        if(di.contains("0000")){
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        int count = 0;
        //每一次将队列里面的锁数字每一个都加1或减一都将结果再次放入队列中看什么时候能到达目标值需要判断走到的锁数字是不是被包含在死锁中中如果被包含就不走这一步
        while(!queue.isEmpty()){
            int size = queue.size();

            while(size-- != 0){
                String s = queue.poll();
                if(s.equals(target)){
                    return count;
                }
                for(int i = 0;i < s.length();i ++){
                    StringBuilder sb1 = new StringBuilder(s);
                    StringBuilder sb2 = new StringBuilder(s);
                    char c1 = sb1.charAt(i);//加
                    char c2 = sb1.charAt(i);//减
                    if(c1 == '9'){//进位应为0
                        c1 = '0';
                    }else{
                        c1 ++;
                    }
                    if(c2 == '0'){//退一位应为0
                        c2 = '9';
                    }else{
                        c2 --;
                    }
                    sb1.setCharAt(i,c1);//修改字符
                    sb2.setCharAt(i,c2);

                    if(!di.contains(sb1.toString()) && !set.contains(sb1.toString())){
                        set.add(sb1.toString());//标记使用过
                        queue.offer(sb1.toString());//入队
                    }
                    if(!di.contains(sb2.toString()) && !set.contains(sb2.toString())){
                        set.add(sb2.toString());
                        queue.offer(sb2.toString());
                    }
                }

            }
            count ++;

        }
        return -1;


    }
}
